class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        ranges = {}
        for i in range(1, 27):
            si = str(i)
            begin = 0
            while True:
                begin = s.find(si, begin)
                if begin==-1:
                    break
                end = begin + len(si) -1
                lastEnd = begin-1
                if end not in ranges:
                    ranges.update({end:[]})
                ranges[end].append(lastEnd)
                begin += 1
        ends = list(ranges.keys())
        ends.sort()
        endWithNumDecodings = {-1:1}
        for end in ends:
            numDecoding = 0
            for lastEnd in ranges[end]:
                if lastEnd in endWithNumDecodings:
                    numDecoding += endWithNumDecodings[lastEnd]
            if end not in endWithNumDecodings:
                endWithNumDecodings.update({end:0})
            endWithNumDecodings[end] += numDecoding
        del endWithNumDecodings[-1]
        if len(s)-1 in endWithNumDecodings:
            return endWithNumDecodings[len(s)-1]
        else:
            return 0

print(Solution().numDecodings(""))